"""
难度：中等
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，
其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 
即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
示例:
输入: [1,2,3,4,5]
输出: [120,60,40,30,24]
提示：
所有元素乘积之和不会溢出 32 位整数
a.length <= 100000
"""
"""
构造一个答案数组 B，长度和数组 A 长度一致。
先从左到右遍历一遍 A 数组，将 A[i] 左侧的元素乘积累积起来，存储到 B 数组中。
再从右到左遍历一遍，将 A[i] 右侧的元素乘积累积起来，再乘以原本 B[i] 的值，
即为 A 中除了 A[i] 之外的其他所有元素乘积。
"""
from typing import List
class Solution:
    def constructArr(self, a: List[int]) -> List[int]:
        size = len(a)
        b = [1 for _ in range(size)]
        left = 1
        # [1,2,3]
        # 1 2  6
        for i in range(size):
            b[i] *= left
            left *= a[i]
        right = 1
        for i in range(size-1, -1, -1):
            b[i] *= right
            right *= a[i]

        return b
if __name__=="__main__":
    a = [1,2,3,4,5]
    solu = Solution()
    print(solu.constructArr(a))